//合并区间（medium）: https://leetcode.cn/problems/merge-intervals/
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // 1. 先按照左端点排序
        sort(intervals.begin(), intervals.end());

            // 2. 合并区间
            int left = intervals[0][0],
                right = intervals[0][1];
        vector<vector<int>> ret;
        for (int i = 1; i < intervals.size(); i++) 
        {
            int a = intervals[i][0], b = intervals[i][1];
            if (a <= right) // 有重叠部分
            {
                // 合并 - 求并集
                right = max(right, b);
            } else // 没有重叠部分
            {
                ret.push_back({left, right}); // 加⼊到结果中
                left = a;
                right = b;
            }
        }
        // 别忘了最后⼀个区间
        ret.push_back({left, right});
        return ret;
    }
};